//
//  SGHCharMatchKMP.m
//  ObjectiveCDemo20200321
//
//  Created by 远平 on 2021/11/25.
//  Copyright © 2021 远平. All rights reserved.
//

#import "SGHCharMatchKMP.h"

//来自：[KMP算法(快速模式匹配算法)详解以及C语言实现](http://data.biancheng.net/view/13.html)
@implementation SGHCharMatchKMP

- (void)test {
    char *ch = "ababcabcacbab";
    char *pattern = "abcac";
//    char *ch = "ababcabcacbabddd";
//    char *pattern = "abcacbabddd";
    int index = KMP(ch, pattern);
    printf("index = %d\n", index);
}

void Next(char *T, int *next) {
    int i = 1;
    next[1] = 0;
    int j = 0;
    while (i < strlen(T)) {
        if (j == 0 || T[i-1] == T[j-1]) {
            i++;
            j++;
#if 0
            //改进
            if (T[i-1] != T[j-1]) {
               next[i] = j;
            } else {
                next[i] = next[j];
            }
#else
            next[i]=j;
#endif
        } else {
            j = next[j];
        }
    }
}

int KMP(char * S,char * T) {
    int next[10];   //FIXME: T的字符长度超过10会崩溃
    Next(T,next);   //根据模式串T,初始化next数组
    int i = 1;
    int j = 1;
    while (i <= strlen(S) && j <= strlen(T)) {
        //j==0:代表模式串的第一个字符就和当前测试的字符不相等；S[i-1]==T[j-1],如果对应位置字符相等，两种情况下，指向当前测试的两个指针下标i和j都向后移
        if (j == 0 || S[i-1] == T[j-1]) {
            i++;
            j++;
        } else {
            j = next[j];//如果测试的两个字符不相等，i不动，j变为当前测试字符串的next值
        }
    }
    if (j > strlen(T)) {//如果条件为真，说明匹配成功
        return i - (int)strlen(T);
    }
    return -1;
}

@end
